﻿'''
题目描述
小明每周上班都会拿到自己的工作清单，工作清单内包含 n 项工作，每项工作都有对应的耗时时间（单位 h）和报酬，工作的总报酬
为所有已完成工作的报酬之和，那么请你帮小明安排一下工作，保证小明在指定的工作时间内工作收入最大化。
输入描述
T 代表工作时长（单位 h， 0 < T < 1000000），
n 代表工作数量（ 1 < n ≤ 3000）。
接下来是 n 行，每行包含两个整数 t，w。
t 代表该工作消耗的时长（单位 h， t > 0），w 代表该项工作的报酬。
输出描述
输出小明指定工作时长内工作可获得的最大报酬。
示例1
输入
40 3
20 10
20 20
20 5
输出
30
解题思路
本题是典型的01背包问题，其中：
工作时长 ( T ) 相当于背包的承重。
每一项工作相当于每件物品。
工作消耗的时长相当于物品的重量。
工作的报酬相当于物品的价值。
思路
初始化与输入：
首先读入工作时间 ( T ) 和工作数量。
读入每项工作的耗时和报酬，存储在二维数组中。
动态规划：
确定所有工作中耗时最短的那个 ( \text{min_time} )，以便从该时间开始计算dp数组。
初始化一个二维dp数组 ( \text{dp}[i][j] )，其中 ( \text{dp}[i][j] ) 表示前 ( i ) 项工作在 ( j ) 时间内能获得的最大报酬。
动态规划执行：
使用两个嵌套的for循环遍历工作项 ( i ) 和时间 ( j )。
对于第 ( i ) 项工作：
如果耗时 ( \text{tasks}[i-1][0] ) 大于 ( j )，则无法完成该项工作，此时最大报酬为 0。
否则，能完成该项工作，最大报酬为 ( \text{tasks}[i-1][1] ) 加上前 ( i-1 ) 项工作在 ( j-\text{tasks}[i-1][0] ) 时间内能
获得的最大报酬。
更新dp数组，( \text{dp}[i][j] = \max(\text{dp}[i-1][j], \text{current}) )，其中 (\text{current}) 是如果包含当前工作所
得到的报酬。
输出结果：
输出 ( \text{dp}[n][T] )，表示前 ( n ) 项工作在 ( T ) 时间内能获得的最大报酬。
'''
#输入描述
#T 代表工作时长（单位 h， 0 < T < 1000000），
#n 代表工作数量（ 1 < n ≤ 3000）。
#接下来是 n 行，每行包含两个整数 t，w。
#t 代表该工作消耗的时长（单位 h， t > 0），w 代表该项工作的报酬。
#输出描述
#输出小明指定工作时长内工作可获得的最大报酬。
'''
示例1
输入
40 3
20 10
20 20
20 5
输出
30
'''

#读取输入
t,n = map(int,input().split())  #工作时长t:背包重量，工作数量n:物品数量

worktime_value = []
for _ in range(n):
    worktime_value.append(list(map(int,input().split())))
#初始化dp,不一定从0开始，1-n,1-t
dp = [[0] * (t + 1) for _ in range(n + 1)]
#防止无效遍历，要获取最小工作时长：即物品重量
min_time = float('inf')
for work in worktime_value:
    min_time = min(min_time,work[0])

#主要是动态规划公式的理解：初始化还有遍历顺序
for i in range(1,n + 1):
    for j in range(min_time, t + 1):
        last = dp[i - 1][j]     #上一项工作在j时间内的最大价值
        current = 0 if worktime_value[i - 1][0] > j else worktime_value[i - 1][1] + dp[i - 1][j - worktime_value[i - 1][0]] 
        dp[i][j] = max(last,current)
#输出n项工作在t时间内的最大报酬dp[n][t]
print(dp[n][t])
